package 三栈;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/13 9:33
 * 逆波兰计算器
 *
 *
 */
public class PolandNotation {
    public static void main(String[] args) {
        //中缀表计算
        String infixExpression = "(30+400)*5-6";

        //中缀转列表
        List<String> list = characterToSuffix(infixExpression);
        System.out.println("中缀表达式=" + list.toString());
        //中缀列表转后缀列表
        List<String> list1 = infixToSuffix(list);
        System.out.println("后缀表达式=" + list1.toString());

        //后缀计算
        int res = calculateSuffixExpression(list1);
        System.out.println("最后结果为" + res);


       /* //后缀计算
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
        List< String > lsit = parseSuffixExpreesionList(suffixExpression);
         res = calculateSuffixExpression(lsit);
        System.out.println("最后结果为" + res);*/

    }

    //中缀转后缀
    public static List< String > infixToSuffix(List< String > list) {
        Stack< String > stack = new Stack<>();
        ArrayList asList = new ArrayList();
        for (String s : list) {

            if ("(".equals(s)) {
                //直接入栈
                stack.add(s);
            } else if (")".equals(s)) {
                //弹出栈中  截止“(”前的所有的运算符
                while (stack.size() > 0 && !("(".equals(stack.peek()))) {
                    //进入列
                    asList.add(stack.pop());
                }
                stack.pop();
            } else if (s.matches("\\d+")) {
                //如果是數字 也直接入列
                asList.add(s);
            } else {
                //如果是运算符则进行判断
                if (stack.size() == 0 || "(".equals(stack.peek())) {
                    //如果是空的  或者 最上面的是（符号 就直接如栈
                    stack.add(s);
                } else {
                    //如果不为空 则进行判断  如果当前的运算符 优先级大于顶上 入列 否则就
                    //弹出栈顶的运算符入列 再和下一个栈顶进行比较  直到栈空 或者
                    if (getPriority(s) > getPriority(stack.peek())) {
                        asList.add(s);
                    } else {
                        while (stack.size() != 0 && (getPriority(s) <= getPriority(stack.peek()))) {
                            asList.add(stack.pop());
                        }
                        //然后把当前运算符放如栈
                        stack.add(s);
                    }
                }
            }
        }



        //遍历完成 再清空栈
        while (stack.size() != 0) {
            asList.add(stack.pop());
        }

        return asList;
    }

    //得到优先级
    public static int getPriority(String operator) {
        char ch = operator.charAt(0);
        switch (ch) {
            case '+':
                return 1;
            case '-':
                return 1;
            case '*':
                return 2;
            case '/':
                return 2;
            default:
                return -1;
        }
    }

    //中缀字符串转列表
    public static List< String > characterToSuffix(String infixExpression) {
        ArrayList< String > list = new ArrayList<>();

        for (int i = 0; i < infixExpression.length(); i++) {


            char c = infixExpression.charAt(i);



            //如果不是数字 直接放入列表
            if (c < '0' || c > '9') {

                list.add(infixExpression.substring(i,i+1));
            } else {

                //如果是数字 就判断是不是后面的也是数字
                String s = infixExpression.substring(i,i+1);


                //判断后面的字符是不是数字
                for (int j = i + 1; j < infixExpression.length(); j++) {
                    char num = infixExpression.charAt(j);
                    if (num < '0' || num > '9') {
                        break;
                    }
                    //把所有的数据加入到字符串中
                    s += infixExpression.substring(j,j+1);
                    //每加一个 i往后移动
                    i++;
                }
                list.add(s);
            }
        }


        //返回这个生成的列表  就是中缀转换的列表
        return list;
    }


    //把对应的表达式放入栈中
    public static List< String > parseSuffixExpreesionList(String suffixExpression) {

        List< String > list = new ArrayList<>();
        //根据空格分割这个表达式  存入集合中
        String[] s = suffixExpression.split(" ");
        for (String s1 : s) {
            list.add(s1);
        }
        return list;
    }

    //后缀进行计算
    public static int calculateSuffixExpression(List< String > list) {
        //创建一个新的栈
        Stack< String > stack = new Stack<>();
        //遍历集合   如果是数字直接添加到栈中  如果是运算符就 取出数字进行运算
        for (String item : list) {
            if ((item.matches("\\d+"))) {//匹配是数字的正则表达式
                //是数字直接添加到栈中
                stack.add(item);
            } else {

                //是运算符就 取出数字进行运算
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res;

                if ("+".equals(item)) {
                    res = num2 + num1;
                } else if ("-".equals(item)) {
                    res = num2 - num1;
                } else if ("*".equals(item)) {
                    res = num2 * num1;
                } else if ("/".equals(item)) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("符号错误");
                }
                //最后吧运算的结果重新添加到栈中
                stack.add(String.valueOf(res));

            }
        }
        //返回栈中最后一个元素
        return Integer.parseInt(stack.pop());
    }
}
